class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

		return AddBinary(a, b);
	}

	string AddBinary(string a, string b) {
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		string c;

		int carry = 0;
		for (int i = 0; i < a.length() || i < b.length() || carry > 0; ++i) {
			if (i < a.length()) {
				carry += a[i] - '0';
			}
			if (i < b.length()) {
				carry += b[i] - '0';
			}
			c += static_cast<char>(carry % 2 + '0');
			carry /= 2;
		}
		reverse(c.begin(), c.end());
		return c;
	}

};